Tic-tac-toe - Implementing Minimax Tree Search

https://thesharperdev.com/implementing-minimax-tree-search


Coding A Perfect Tic-Tac-Toe Bot!

https://thesharperdev.com/coding-the-perfect-tic-tac-toe-bot


How many Tic-Tac-Toe (noughts and crosses) games are possible?

http://www.se16.info/hgb/tictactoe.htm


Winning Tic-tac-toe Strategies

https://www.instructables.com/Winning-tic-tac-toe-strategies/

	
Tic Tac Toe - John von Neumann's minimax algorithm.

https://www.half-real.net/tictactoe


REM ...................................................................................................................................................................

Rowan Gilmore, studied at University of Cambridge

There are 255168 possible game of Tic-tac-toe excluding symmetry. The first player wins 131184 of these, the second player wins 77904 games and the remaining 46080 are drawn.

As has been pointed out, with best play all games should result in a draw. Hence although there are 209088 winning games, many of these would almost never occur in practice.

For those interested, the python code I used to simulate this is given below:


nWinO, nWinX, nDraw = 0, 0, 0 
 
def recurse(board, toMove): 
    global nWinO, nWinX, nDraw 
 
    def win(board, player): 
        return (any(all(board[i][j] == player for j in range(3)) for i in range(3)) or 
                any(all(board[i][j] == player for i in range(3)) for j in range(3)) or 
                all(board[i][i] == player for i in range(3)) or 
                all(board[i][2-i] == player for i in range(3))) 
 
    def draw(board): return all(board[i][j] != '' for i in range(3) for j in range(3)) 
 
    if win(board, 'O'): nWinO += 1 
    elif win(board, 'X'): nWinX += 1 
    elif draw(board): nDraw += 1 
    else: 
        for i in range(3): 
            for j in range(3): 
                if board[i][j] == '': 
                    board[i][j] = toMove 
                    recurse(board, 'X' if toMove == 'O' else 'O') 
                    board[i][j] = '' 
 
recurse([['','',''],['','',''],['','','']], 'O') 
 
print("There are %d possible games (excluding symmetry), of which O wins %d, X wins %d and %d are drawn." % (nWinO+nWinX+nDraw,nWinO,nWinX,nDraw)) 


REM ..................................................................................................................................................................


Below a simple Tic Tac Toe Program in C

#include <stdio.h>
#include <conio.h>

char square[10] = { 'o', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

int checkwin();
void board();

int main()
{
    int player = 1, i, choice;

    char mark;
    do
    {
        board();
        player = (player % 2) ? 1 : 2;

        printf("Player %d, enter a number:  ", player);
        scanf("%d", &choice);

        mark = (player == 1) ? 'X' : 'O';

        if (choice == 1 && square[1] == '1')
            square[1] = mark;
            
        else if (choice == 2 && square[2] == '2')
            square[2] = mark;
            
        else if (choice == 3 && square[3] == '3')
            square[3] = mark;
            
        else if (choice == 4 && square[4] == '4')
            square[4] = mark;
            
        else if (choice == 5 && square[5] == '5')
            square[5] = mark;
            
        else if (choice == 6 && square[6] == '6')
            square[6] = mark;
            
        else if (choice == 7 && square[7] == '7')
            square[7] = mark;
            
        else if (choice == 8 && square[8] == '8')
            square[8] = mark;
            
        else if (choice == 9 && square[9] == '9')
            square[9] = mark;
            
        else
        {
            printf("Invalid move ");

            player--;
            getch();
        }
        i = checkwin();

        player++;
    }while (i ==  - 1);
    
    board();
    
    if (i == 1)
        printf("==>\aPlayer %d win ", --player);
    else
        printf("==>\aGame draw");

    getch();

    return 0;
}

/*********************************************

FUNCTION TO RETURN GAME STATUS
1 FOR GAME IS OVER WITH RESULT
-1 FOR GAME IS IN PROGRESS
O GAME IS OVER AND NO RESULT
 **********************************************/

int checkwin()
{
    if (square[1] == square[2] && square[2] == square[3])
        return 1;
        
    else if (square[4] == square[5] && square[5] == square[6])
        return 1;
        
    else if (square[7] == square[8] && square[8] == square[9])
        return 1;
        
    else if (square[1] == square[4] && square[4] == square[7])
        return 1;
        
    else if (square[2] == square[5] && square[5] == square[8])
        return 1;
        
    else if (square[3] == square[6] && square[6] == square[9])
        return 1;
        
    else if (square[1] == square[5] && square[5] == square[9])
        return 1;
        
    else if (square[3] == square[5] && square[5] == square[7])
        return 1;
        
    else if (square[1] != '1' && square[2] != '2' && square[3] != '3' &&
        square[4] != '4' && square[5] != '5' && square[6] != '6' && square[7] 
        != '7' && square[8] != '8' && square[9] != '9')

        return 0;
    else
        return  - 1;
}


/*******************************************************************
FUNCTION TO DRAW BOARD OF TIC TAC TOE WITH PLAYERS MARK
 ********************************************************************/


void board()
{
    system("cls");
    printf("\n\n\tTic Tac Toe\n\n");

    printf("Player 1 (X)  -  Player 2 (O)\n\n\n");


    printf("     |     |     \n");
    printf("  %c  |  %c  |  %c \n", square[1], square[2], square[3]);

    printf("_____|_____|_____\n");
    printf("     |     |     \n");

    printf("  %c  |  %c  |  %c \n", square[4], square[5], square[6]);

    printf("_____|_____|_____\n");
    printf("     |     |     \n");

    printf("  %c  |  %c  |  %c \n", square[7], square[8], square[9]);

    printf("     |     |     \n\n");
}

/*******************************************************************
END OF PROJECT
 ********************************************************************/

REM ..................................................................................................................................................................

Below a simple Tic Tac Toe Program in Python


square = [0,1,2,3,4,5,6,7,8,9]

def main():
    player = 1
    status = -1

    while status== -1:
        board()
        
        if player%2 == 1:
            player = 1
        else:
            player = 2

        print('\nPlayer', player)
        choice = int(input('Enter a number:'))

        if player == 1:
            mark = 'X'
        else:
            mark = 'O'

        if choice == 1 and square[1] == 1:
            square[1] = mark
        elif choice == 2 and square[2] == 2:
            square[2] = mark
        elif choice == 3 and square[3] == 3:
            square[3] = mark
        elif choice == 4 and square[4] == 4:
            square[4] = mark
        elif choice == 5 and square[5] == 5:
            square[5] = mark
        elif choice == 6 and square[6] == 6:
            square[6] = mark
        elif choice == 7 and square[7] == 7:
            square[7] = mark
        elif choice == 8 and square[8] == 8:
            square[8] = mark
        elif choice == 9 and square[9] == 9:
            square[9] = mark
        else:
            print('Invalid move ')
            player -= 1
                
        status = game_status()
        player += 1
            
    print('RESULT')    
    if status == 1:
        print('Player',player-1,'win')
    else:
        print('Game draw')


###############################################
#    FUNCTION TO RETURN GAME STATUS
#    1 FOR GAME IS OVER WITH RESULT
#    -1 FOR GAME IS IN PROGRESS
#    O GAME IS OVER AND NO RESULT
###############################################

def game_status():
    if square[1] == square[2] and square[2] == square[3]:
        return 1
    elif square[4] == square[5] and square[5] == square[6]:
        return 1
    elif square[7] == square[8] and square[8] == square[9]:
        return 1
    elif square[1] == square[4] and square[4] == square[7]:
        return 1
    elif square[2] == square[5] and square[5] == square[8]:
        return 1
    elif square[3] == square[6] and square[6] == square[9]:
        return 1
    elif square[1] == square[5] and square[5] == square[9]:
        return 1
    elif square[3] == square[5] and square[5] == square[7]:
        return 1
    elif square[1] != 1 and square[2] != 2 and square[3] != 3 and square[4] != 4 and square[5] != 5 and square[6] != 6 and square[7] != 7 and square[8] != 8 and square[9] != 9:
        return 0
    else:
        return -1



###############################################
#    FUNCTION TO DRAW BOARD
#    OF TIC TAC TOE WITH PLAYERS MARK
###############################################


def board():
    print('\n\n\tTic Tac Toe\n\n')

    print('Player 1 (X)  -  Player 2 (O)' ) 
    print()

    print('     |     |     ' )
    print(' ' ,square[1] ,' | ' ,square[2] ,' |  ' ,square[3] )

    print('_____|_____|_____' )
    print('     |     |     ' )

    print(' ' ,square[4] ,' | ' ,square[5] ,' |  ' ,square[6] )

    print('_____|_____|_____' )
    print('     |     |     ' )

    print(' ' ,square[7] ,' | ' ,square[8] ,' |  ' ,square[9] )

    print('     |     |     ' )

main()







